package first.codeTop.alibaba;

/**
 * @ClassName LC5
 * @description:
 * @author: 荣燊
 * @create: 2021-10-16 13:07
 **/
public class LC5 {
    public static void main(String[] args) {

    }

    //最长回文字符串，动态递归法
    public static String longestPalindrome(String s) {
        //字符串的第i位到第j位是不是回文
        boolean[][] dp = new boolean[s.length()][s.length()];
        //初始化,从第i位到第i为肯定是回文字符串
        for (int i=0; i<s.length(); i++) {
            dp[i][i] = true;
        }
        //
        char[] chars = s.toCharArray();
        int len = s.length();
        int begin = 0;
        int maxLen = 1;
        //
        for (int l=1; l<len; l++) {
            for (int i=0; i<len; i++) {
                int j = i + l;
                //j越界
                if (j >= len) {
                    break;
                }
                //开始动态规划
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    // 如果该回文字符串只有3位，那么j-i=2
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //求最大的maxLen
                if (dp[i][j] && j-i+1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin+maxLen);
    }
}
